//给你一个整数数组 nums，请你找出并返回能被三整除的元素 最大和。 
//
// 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [3,6,5,1,8]
//输出：18
//解释：选出数字 3, 6, 1 和 8，它们的和是 18（可被 3 整除的最大和）。 
//
// 示例 2： 
//
// 
//输入：nums = [4]
//输出：0
//解释：4 不能被 3 整除，所以无法选出数字，返回 0。
// 
//
// 示例 3： 
//
// 
//输入：nums = [1,2,3,4,4]
//输出：12
//解释：选出数字 1, 3, 4 以及 4，它们的和是 12（可被 3 整除的最大和）。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 4 * 10⁴ 
// 1 <= nums[i] <= 10⁴ 
// 
//
// Related Topics 贪心 数组 动态规划 排序 👍 408 👎 0


package LeetCode.editor.cn;

import java.util.Arrays;

/**
  * @date 2025-11-23 23:17:20
  * @description 1262.可被三整除的最大和
*/
public class GreatestSumDivisibleByThree {
    public static void main(String[] args) {
        GreatestSumDivisibleByThree fun = new GreatestSumDivisibleByThree();
        Solution solution = fun.new Solution();
        System.out.println(solution.maxSumDivThree(new int[]{3,6,5,1,8}));
//        System.out.println(solution.maxSumDivThree(new int[]{2,6,2,2,7}));
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        // 不能被三整除的数字，要么余1，要么余2
        // 遍历数组，将数字分为余1和余2的数组
        // 遍历余1的数组，将数字加到结果中，并记录最小的两个数字
         // 遍历余2的数组，将数字加到结果中，并记录最小的数字
        public int maxSumDivThree1(int[] nums) {
            int res = 0;
            int one1 = Integer.MAX_VALUE, one2 = Integer.MAX_VALUE;
            int two1 = Integer.MAX_VALUE, two2 = Integer.MAX_VALUE;

            for (int num : nums) {
                switch (num % 3) {
                    case 1:
                        res += num;
                        // 更新余数为1的最小两个值
                        if (num < one1) {
                            one2 = one1;
                            one1 = num;
                        } else if (num < one2) {
                            one2 = num;
                        }
                        break;
                    case 2:
                        res += num;
                        // 更新余数为2的最小两个值
                        if (num < two1) {
                            two2 = two1;
                            two1 = num;
                        } else if (num < two2) {
                            two2 = num;
                        }
                        break;
                    default:
                        res += num;
                        break;
                }
            }

            int mod = res % 3;
            if (mod == 0) return res;

            if (mod == 1) {
                // 移除1个余数为1的最小值，或者移除2个余数为2的最小值
                int option1 = (one1 != Integer.MAX_VALUE) ? one1 : Integer.MAX_VALUE;
                int option2 = (two1 != Integer.MAX_VALUE && two2 != Integer.MAX_VALUE) ? two1 + two2 : Integer.MAX_VALUE;
                return res - Math.min(option1, option2);
            } else { // mod == 2
                // 移除1个余数为2的最小值，或者移除2个余数为1的最小值
                int option1 = (two1 != Integer.MAX_VALUE) ? two1 : Integer.MAX_VALUE;
                int option2 = (one1 != Integer.MAX_VALUE && one2 != Integer.MAX_VALUE) ? one1 + one2 : Integer.MAX_VALUE;
                return res - Math.min(option1, option2);
            }
        }



        // 动态规划
        public int maxSumDivThree2(int[] nums) {
            // f[i][j] 表示前 i 个数字中，余数 j 的最大和,
            //这些数的和的最大值。那么对于当前的数 nums[i]
            // 如果我们选取它，那么就可以通过 f(i−1,(j−nums[i])mod3) 转移得来；
            // 如果我们不选取它，就可以通过 f(i−1,j) 转移得来。因此我们可以写出如下的状态转移方程：
            // f[i][j] = max(f[i-1][(j-nums[i])%3], f[i-1][j])
            // 初始状态为f(0,0)=0，以及 f(0,1)=f(0,2)=Integer.MIN_VALUE
            // 同时做空间优化
            int[] f = {0, Integer.MIN_VALUE, Integer.MIN_VALUE};
            for (int num : nums) {
                int[] g = new int[3];
                // 先保存f
                System.arraycopy(f, 0, g, 0, 3);
                for (int i = 0; i < 3; ++i) {
                    // 加上序号i 防止溢出
                    // 代表不选和选
                    g[(i + num % 3) % 3] = Math.max(g[(i + num % 3) % 3], f[i] + num);
                }
                f = g;
            }
            return f[0];
        }

        //dfs+ memo
        public int maxSumDivThree3(int[] nums) {
            int n = nums.length;
            int[][] memo = new int[n][3];
            for (int i = 0; i < n; i++)
                Arrays.fill(memo[i], -1); // -1 表示没有计算过
            return dfs(memo, nums, n - 1, 0);
        }

        private int dfs(int[][] memo, int[] nums, int i, int j) {
            if (i < 0) return j == 0 ? 0 : Integer.MIN_VALUE;
            if (memo[i][j] != -1) return memo[i][j]; // 之前计算过
            return memo[i][j] = Math.max(dfs(memo, nums, i - 1, j),
                    dfs(memo, nums, i - 1, (j + nums[i]) % 3) + nums[i]);
        }
        // 动态规划

        public int maxSumDivThree4(int[] nums) {
            int n = nums.length;
            var f = new int[n + 1][3];
            f[0][1] = f[0][2] = Integer.MIN_VALUE;
            for (int i = 0; i < n; i++)
                for (int j = 0; j < 3; j++)
                    f[i + 1][j] = Math.max(f[i][j], f[i][(j + nums[i]) % 3] + nums[i]);
            return f[n][0];
        }
        // 滚动数组
        public int maxSumDivThree(int[] nums) {
            int n = nums.length;
            // 用一个二维数组保存中间结果，用滚动数组优化
            var f = new int[2][3];
            f[0][1] = f[0][2] = Integer.MIN_VALUE;
            for (int i = 0; i < n; i++)
                for (int j = 0; j < 3; j++)
                    f[(i + 1) % 2][j] = Math.max(f[i % 2][j], f[i % 2][(j + nums[i]) % 3] + nums[i]);
            return f[n % 2][0];
        }




}
//leetcode submit region end(Prohibit modification and deletion)

} 
